# 2008.7  gothic64@freechal.com

import operator

class PrimeFactor(list):
    """ 
    multiply of Prime Numbers
    
    list of Prime Factors
    Element is [base, exponential]
    ex 2*2*2*3*3*5 is represented by [[2,3], [3,2], [5,1]] 
    """
    
    def __init__(self, data=[]):
        
        self.primeNumbers = [2, 3, 5, 7, 11, 13, 17, 19]
        
        
        if operator.isNumberType(data):
            list.__init__(self)
            
            num = data
            if num < 2:
                list.append(self,[num, 1])
            else:            
                prevDenom = 2
                denom = 2
                count = 0
                while not self.isPrimeNumber(num):
                    if num % denom == 0:
                        num /= denom
                        
                        if denom == prevDenom:
                            count +=1
                        else:
                            if  count > 0:
                                list.append(self, [prevDenom, count])
                            prevDenom = denom
                            count = 1
                    else:
                        denom = self.getNextPrimeNumber(denom)
                    # print denom, num
                        
                if denom == num:
                    count +=1
                else:
                    if count > 0:
                        list.append(self, [denom, count])
                    denom = num
                    count = 1
                    
                list.append(self, [denom, count])
            
        else:
            list.__init__(self, data)

    def __repr__(self):
        ret = ""
        for pf in self:
            if ret != "" :
                ret += "*"
            ret += str(pf[0])
            
            if pf[1] != 1:
                ret += "^" + str(pf[1]) 
        return ret
    
    def __int__(self):
        val = 1
        for pf in self:
            val *= pf[0]**pf[1]
        return val
    
    def __and__(self, other):
        """  & operator overloading:GCM(greatest common measure) """
        
        s, o = 0, 0
        
        gcm = PrimeFactor()
        
        while s < len(self) and o < len(other):
            ss = self[s]
            oo = other[o]
                                    
            if ss[0]==oo[0]:
                gcm.append([ss[0], min(ss[1], oo[1])])
                s += 1
                o += 1
            elif ss[0] > oo[0] :
                o += 1
            else:
                s += 1   
        
        return gcm
    
    def __or__(self, other):
        """ | operator overloading: LCM( least common multiple )"""
        s, o = 0, 0
        
        lcm = PrimeFactor()
        
        while s < len(self) and o < len(other):
            ss = self[s]
            oo = other[o]
            
            if ss[0]==oo[0]:
                lcm.append([ss[0], max(ss[1], oo[1])])
                s += 1
                o += 1
            elif ss[0] > oo[0] :
                lcm.append(oo)
                o += 1
            else:
                lcm.append(ss)
                s += 1
                
        if s < len(self):
            for remain in self[s:]: 
                lcm.append(remain)
        
        if o < len(other):
            for remain in other[o:]: 
                lcm.append(remain)
            
        return lcm

    def __div__(self, other):
        """  & operator overloading:GCM(greatest common measure) """
        return int(self) / int(other)
        
    def isPrimeNumber(self, num):
        """ if  parameter num is prime number, it returns True"""
        
        try :
            i = self.primeNumbers.index(num)
            return True
        except ValueError:        
            if num < 2:
                return False
            else:
                i = 2
                while i*i <= num:
                    if num % i == 0:
                        return False
                    else:
                        i = self.getNextPrimeNumber(i)            
                return True
        
    
    def getNextPrimeNumber(self, num):
        """ it returns prime number after num, num should be prime number"""
        
        i = self.primeNumbers.index(num)
        if i < len(self.primeNumbers) - 1:
            return self.primeNumbers[i + 1]
        else:
            num += 2
            while not self.isPrimeNumber(num):
                num += 2
            
            self.primeNumbers.append(num)
            return num
                
    

def getLCM(num1, num2):
    return int(PrimeFactor(num1) | PrimeFactor(num2)) 
 
def getGCM(num1, num2):
    return int(PrimeFactor(num1) & PrimeFactor(num2)) 
 
 

""" 
a = PrimeFactor(9304682830147)
print a
#print a.primeNumbers


print getGCM(5, 6)
p = PrimeFactor(2*3*7)
q = PrimeFactor(3*3*7*11)
print p, q
print (p | q)
print (p & q), int(p&q)
print int(p)
      
#print factor(144), noteText(factor(144))


for i in range(1, 101):
    print PrimeFactor(i)
"""